/**
 * Created with IntelliJ IDEA
 * Description:
 * User: YKH
 * Date: 2022-05-08
 * Time: 16:16
 * author:MyDoubleList
 */
public class MyDoubleList {
    static class Node {
        private int val;
        private Node prev; //前驱指针
        private Node next; //后驱指针

        public Node(int val) {
            this.val = val;
        }
    }

    Node head; //头结点
    Node last; //尾节点

    //打印链表
    public void display() {
        Node cur = head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }

    //头插法
    public void addFist(int val) {
        Node newnode = new Node(val);
        newnode.prev = null;
        //如果链表为空直接 ,将新节点变为头结点
        if (this.head == null) {
            head = newnode;
            last = newnode;
        } else {
            newnode.next = head;
            head.prev = newnode;
            head = newnode;
        }
    }

    //尾插法
    public void addRear(int val) {
        Node newnode = new Node(val);
        newnode.next = null;
        //如果链表为空直接 ,将新节点变为尾结点
        if (last == null) {
            head = newnode;
            last = newnode;
        } else {
            newnode.prev = last;
            last.next = newnode;
            last = newnode;
        }
    }

    //获取链表长度
    public int getsize() {
        int size = 0;
        Node cur = head;
        while (cur != null) {
            size++;
            cur = cur.next;
        }
        return size;
    }

    //任意位置插入数据,第一个节点下标默认为 0
    public void insert(int val, int index) {
        //判断插入的位置是否合法
        if (index < 0 || index > getsize()) {
            System.out.println("输入的位置不合法");
            return;
        }
        //头插,插入位置为头结点
        if (index == 0) {
            addFist(val);
            return;
        }
        //尾插,插入位置为尾节点
        if (index == getsize()) {
            addRear(val);
            return;
        }
        //插入位置在中间
        Node cur = head;
        int count = 0;
        while (cur != null) {
            if (count == index) {
                Node newnode = new Node(val);
                newnode.prev = cur.prev;
                newnode.next = cur;
                cur.prev.next = newnode;
                cur.prev = newnode;
                return;
            }
            count++;
            cur = cur.next;
        }
    }
        //查找是否包含关键字key是否在单链表当中
        public boolean contains ( int key){
            if (head == null) {
                System.out.println("链表为空");
                return false;
            }
            Node cur = head;
            while(cur!=null) {
                if( cur.val == key) {
                    return true;
                }
                cur = cur.next;
            }
            return false;
        }
        //删除第一次出现关键字为key的节点
        public void remove(int key){
            //判断链表为空
            if (head == null) {
                System.out.println("链表为空");
                return ;
            }
            //判断要删除的是头结点
            if( head.val == key) {
                head = head.next;
            }
            //要删除的是中间节点
            Node cur = head;
            while(cur!=null) {
                if( cur.val == key) {
                    cur.prev.next = cur.next;
                    //判断要删除的是最后一个节点
                    if(cur.next != null) {
                        cur.next.prev = cur.prev;
                    } else {
                        last = cur.prev;
                    }
                    return ;
                }
                cur = cur.next;
            }
        }
        //删除所有值为key的节点
        public void removeAllKey(int key){
            if (head == null) {
                System.out.println("链表为空");
                return ;
            }
            while( head.val == key) {
                head = head.next;
                if(head == null) {
                    return;
                }
            }
            Node cur = head;
            while(cur!=null) {
                if( cur.val == key) {
                    cur.prev.next = cur.next;
                    if(cur.next != null) {
                        cur.next.prev = cur.prev;
                    } else {
                        last = cur.prev;
                    }
                    cur = cur.next;
                } else {
                    cur = cur.next;
                }
            }
        }
        //清空链表
        public void clear(){
            //head = null; //暴力解法
            Node cur = head;
            head = null;
            while( cur != null) {
                Node temp = cur.next;
                cur.prev = null;
                cur.next = null;
                cur = temp;
            }
        }
}
